/**
 * 队列实现栈
 */
#include <iostream>
#include <stdexcept>

using namespace std;

template <typename T>
class Queue
{
    struct Node
    {
        T data;     // 数据
        Node *next; // 指针
        Node() : next(nullptr) {}
        Node(T t) : data(t), next(nullptr) {}
        Node(T t, Node *n) : data(t), next(n) {}
    };

private:
    Node *front; // 头
    Node *rear;  // 尾
    int size;

public:
    Queue() : front(nullptr), rear(nullptr), size(0) {}
    ~Queue();

    void enqueue(T element); // 入队
    T dequeue();             // 出队
    T getFront() const;      // 获取头
    int getSize() const;     // 获取大小
    void print();            // 打印
    bool empty() const;
};

template <typename T>
Queue<T>::~Queue()
{
    while (front)
    {
        Node *pTemp = front;
        front = front->next;
        delete pTemp;
    }
    delete rear;
}

template <typename T>
void Queue<T>::enqueue(T element)
{
    Node *newNode = new Node(element);
    if (rear == nullptr)
    {
        rear = newNode;
        front = rear;
    }
    else
    {
        rear->next = newNode;
        rear = newNode;
    }
    ++size;
}

template <typename T>
T Queue<T>::dequeue()
{
    if (front == nullptr)
    {
        throw std::underflow_error("Queue is empty");
    }
    T element = front->data;
    Node *pTemp = front;
    front = front->next;
    delete pTemp;
    --size;
    if (size == 0)
    {
        rear == nullptr;
    }
    return element;
}

template <typename T>
T Queue<T>::getFront() const
{
    if (front == nullptr)
    {
        throw std::underflow_error("Queue is empty");
    }
    return front->data;
}

template <typename T>
int Queue<T>::getSize() const
{
    return size;
}

template <typename T>
bool Queue<T>::empty() const
{
    return size == 0;
}

template <typename T>
void Queue<T>::print()
{
    while (front)
    {
        cout << front->data << " ";
        dequeue();
    }
    cout << endl;
}

class MyStack
{
private:
    Queue<int> q1;  // 主队列
    Queue<int> q2;  // 副队列
public:
    MyStack(/* args */);
    ~MyStack();
    // 入队
    void push(int x) 
    {
        q1.enqueue(x);
    }
    // 出队
    int pop()
    {
        while (q1.getSize() > 1)
        {
            q2.enqueue(q1.dequeue());
        }
        int result = q1.dequeue();
        while (!q2.empty())
        {
            q1.enqueue(q2.dequeue());
        }
        return result;       
    }
    // 获取队首元素
    int top() 
    {
        while (q1.getSize() > 1)
        {
            q2.enqueue(q1.dequeue());
        }
        int result = q1.dequeue();
        q2.enqueue(result);
        while (!q2.empty())
        {
            q1.enqueue(q2.dequeue());
        }
        return result; 
    }
    // 是否为空
    bool empty()
    {
        return q1.empty();
    }
};

MyStack::MyStack(/* args */)
{
}

MyStack::~MyStack()
{
}
